package algorithm.leetcode.medium;

/*
 给定一个经过编码的字符串，返回它解码后的字符串。
 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数
 */

import java.util.LinkedList;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/21
 */
public class Question394 {

    public static void main(String[] args) {
        String s = "3[a2[c]]";
        Question394 question = new Question394();
        String decodeString = question.decodeString(s);
        System.out.println(decodeString);
    }

    /**
     * 思路：
     * 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算
     * 当 c 为字母时，在 sb 尾部添加 c
     * 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0
     *      记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作
     *      记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串
     *      进入到新 [ 后，res 和 multi 重新记录
     * 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res
     *      last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a
     *      cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2
     */
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        int multi = 0;
        // 记录数字
        LinkedList<Integer> stackMulti = new LinkedList<>();
        LinkedList<String> stackRes = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '[') {
                // 开始记录数字
                stackMulti.push(multi);
                multi = 0;
                // 保持 [ 之前的字母
                stackRes.push(sb.toString());
                sb = new StringBuilder();
            }else if (c == ']') {
                StringBuilder temp = new StringBuilder();
                int curMulti = stackMulti.pop();
                for (int i = 0; i < curMulti; i++) {
                    temp.append(sb);
                }
                // 重新组装 [ 之前的字符 + 加密的字符
                sb = new StringBuilder(stackRes.pop() + temp);
            }else if (c >= '0' && c <= '9') {
                // 是数字
                multi = multi * 10 + Integer.parseInt(c + "");
            }else {
                // 如果字母直接拼接到sb
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
